package com;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleWeightedGraph;

public class TSCheapIns {
	
	/*This method uses the cheap insertion method algorithm to solve TS.*/
	
	static double compute(SimpleWeightedGraph<Node, DefaultWeightedEdge> graph) {
		 
		//Initialise minDist to zero.
		double minDist = 0.0;
		
		double smallestEdge;
		
		//A variable holding the next potential node to visit in the tour.
		Node possibleNextNode = null;
		
		//A variable that holds whether possibleNextNode should be added at start or end of tour.
		String addWhere = "";
		
		//HashSet offers constant-time performance on the 'contains' operation, the only one we need.
		HashSet<Node> visitedNodes = new HashSet<Node>();
		
		//Get all nodes in the graph.
		Set<Node> vertices = graph.vertexSet();
		
		//Pick any vertex and set it as the first node of the tour.
		Iterator<Node> iterN = vertices.iterator();
		Node firstNode = iterN.next();
		
		//Pick another vertex and set it as the last node of the tour.
		Node lastNode = iterN.next();
		
		//Mark the last node as visited. (the first node gets marked inside the loop)
		visitedNodes.add(lastNode);
		
		//Add the weight of the edge connecting these two nodes to the answer.
		minDist += graph.getEdgeWeight(graph.getEdge(firstNode, lastNode));
		
		//Set the first node to be the active node. (I could have chosen the last node instead if I wanted)
		Node activeNode = firstNode;

		//Iterate through the vertices.
		while (visitedNodes.size() < vertices.size()) {
				//reset to infinity at start of new vertex.
				smallestEdge = Double.POSITIVE_INFINITY;
			
				//Iterate through all the edges connected to the vertex.
				Set<DefaultWeightedEdge> edgesFromNode = graph.edgesOf(activeNode);
				Iterator<DefaultWeightedEdge> iterE = edgesFromNode.iterator();
				while (iterE.hasNext()) {
									//Get a random edge connected to the vertex.
									DefaultWeightedEdge edge = iterE.next();
									//Find the target vertex of the edge.
									Node node = graph.getEdgeSource(edge);
									Node targetNode;
									if (node.equals(activeNode)) {targetNode = graph.getEdgeTarget(edge);}
									else {targetNode = node;}
									//Calculate its distance to the first and last nodes of the tour.
									double distToFirst = graph.getEdgeWeight(graph.getEdge(targetNode, firstNode));
									double distToLast = graph.getEdgeWeight(graph.getEdge(targetNode, lastNode));
									//Find the smallest of these two values.
									double smallestWeight = Math.min(distToFirst, distToLast);
									//If the target node is unvisited and if the weight is smaller than the 
									//ones seen so far, update values and pointers.
									if (smallestWeight < smallestEdge && !visitedNodes.contains(targetNode)) {
											if (distToFirst <= distToLast) {smallestEdge = smallestWeight;
								   											possibleNextNode = targetNode;
								   											addWhere = "start";}
											else {smallestEdge = smallestWeight;
												  possibleNextNode = targetNode;
												  addWhere = "end";}
									}
									else {}
				}
				//Mark the current vertex as 'visited'.
				visitedNodes.add(activeNode);
				//Test if we are at the last vertex, where smallestEdge doesnt get updated 
				//so it stays as infinity. in that case, update minTime with edge from last 
				//vertex back to the 1st one. otherwise, update with weight of this edge.
				if (smallestEdge != Double.POSITIVE_INFINITY) {minDist += smallestEdge;}
				else {minDist += graph.getEdgeWeight(graph.getEdge(firstNode, lastNode));}
				//Add the current vertex to the start or end of tour accordingly.
				if (addWhere == "start") {firstNode = possibleNextNode;}
				else {lastNode = possibleNextNode;}
				//Update the pointer to the next vertex to be visited.
				activeNode = possibleNextNode;
		}
		
		
		return minDist;
	}
}
		